翻訳と辞書 Words near each other ・ Fiat Veicoli Industriali ・ Fiat X1/23 ・ Fiat X1/9 ・ Fiat Zero ・ Fiat, Indiana ・ Fiat, Kansas ・ Fiat-Abarth 750 ・ Fiat-Materfer (Buenos Aires Underground) ・ Fiat-Omsky armoured car ・ Fiat-Revelli machine gun ・ Fiatallis ・ Fiatau Penitala Teo ・ Fiatt, Illinois ・ Fiat–Revelli Modello 1914 ・ Fiat–Revelli Modello 1935 ・ Fiat–Shamir heuristic ・ Fiavè ・ Fiazaman ・ Fiałki ・ Fiałkowo ・ FIA–FOTA dispute ・ Fib ・ Fib (poetry) ・ FIB Champions Cup ・ FIBA ・ FIBA 3x3 Under-18 World Championship ・ FIBA 3x3 World Championships ・ FIBA 3x3 World Tour ・ FIBA Africa ・ FIBA Africa Championship 1962 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Fiat–Shamir heuristic ： ウィキペディア英語版 Fiat–Shamir heuristic The Fiat–Shamir heuristic is a technique in cryptography for taking an interactive proof of knowledge and creating a digital signature based on it. This way, some fact (for example, knowledge of a certain number secret to the public) can be proven without revealing underlying information. The technique is due to Fiat and Shamir (1986).〔Amos Fiat and Adi Shamir: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. CRYPTO 1986: pp. 186-194〕 The original interactive proof must have the property of being public-coin, for the method to work. For the algorithm specified below, a reader should be familiar with the laws of modular arithmetic, especially with multiplicative groups of integers modulo n with prime ''n''. The heuristic was originally presented without a proof of security; later, Pointcheval and Stern 〔David Pointcheval and Jacques Stern: Security Proofs for Signature Schemes. EUROCRYPT 1996: pp. 387-398〕 proved its security against chosen message attacks in the ''random oracle model'', that is, under the assumption that random oracles exist. In the case that random oracles don't exist, the Fiat–Shamir heuristic has been proven insecure by Goldwasser and Kalai.〔Shafi Goldwasser and Yael Kalai: On the (In)security of the Fiat-Shamir Paradigm. FOCS 2003: pp. 102〕 The Fiat–Shamir heuristic thus demonstrates a major application of random oracles. If the hash value used below does not depend on the (public) value of ''y'', the security of the scheme is weakened, as a malicious prover can then select a certain value ''x'' so that the product ''cx'' is known. More generally, the Fiat–Shamir heuristic may also be viewed as converting a public-coin interactive proof of knowledge into a non-interactive proof of knowledge. If the interactive proof is an identification protocol, then the non-interactive version can be used directly as a digital signature. ==Example== Here is an interactive proof of knowledge of a discrete logarithm. # Alice want to prove to Bob that she knows $x$: the discrete logarithm of $y\; =\; g^x$ to the base $g$. # She picks a random $v\backslash in\; \backslash Z\_q$, computes $t\; =\; g^v$ and sends $t$ to Bob. # Bob picks a random $c\backslash in\; \backslash Z^$ *_q and sends it to Alice. # Alice computes $r\; =\; v\; -\; cx$ and returns $r$ to Bob. # He checks if $t\; \backslash equiv\; g^ry^c$ (it holds, because $g^ry^c\; =\; g^g^\; =\; g^v\; =\; t$). Fiat-Shamir heuristic allows to replace the interactive step 3 with a non-interactive random oracle access. In practice, we can use a cryptographic hash function instead. # Alice want to prove that she knows $x$: discrete logarithm of $y\; =\; g^x$ to the base $g$. # She picks a random $v\backslash in\backslash Z\_q$ and computes $t\; =\; g^v$. # Alice computes $c\; =\; H(g,y,t)$, where $H()$ is a cryptographic hash function. # She computes $r\; =\; v\; -\; cx$. The resulting proof is the pair $(t,r)$. Since $r$ is an exponent of $g$, the modulus would be $q-1$. # Anyone can check if $t\; \backslash equiv\; g^ry^c$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fiat–Shamir heuristic」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.